In a network switch that performs a flow based lookup, packets are classified into “flows”, where a flow defines a particular communication session between two hosts and is defined by IP source and destination addresses and other fields from a packet header received at the network switch.
When a packet is processed at the network switch, its fields are extracted to form a flow key which is used by a lookup process to identify the packet and process the packet based on the control and state maintained for that flow. When a new flow is received a unique flow key is formed that includes source and destination addresses of the hosts and other fields included in packet headers. The flow keys are stored in a memory structure called a flow table. The location in the flow table that stores the flow key is accessed by a hash lookup using an hkey which is an abbreviated version or “hash” of the flow key. A number of different flow keys can be hashed to the same hkey because the hkey is smaller that the flow key.
New flows are created and their flow keys are stored in a flow directory for later lookup. The flow directory is a memory structure that is organized to implement a typical hash structure. A hash lookup can be performed, for example, using a polynomial function to directly compute the memory location in which a new flow should be stored and where existing flows are looked up. Each location in the flow table, called a bucket id, can store N (a positive integer) different flows having flow keys which hash to the same location, where N is an architecture parameter. When any bucket is full, new flows that can potentially be mapped to that bucket will not be added, i.e., the switch runs out of flow capability at that point. When N flow keys are mapped to the same bucket then the bucket is full and no further flow keys can be mapped to the bucket. A properly selected polynomial function can make sure a bucket will not be full unless most (about 80%) of the buckets are full.